题目描述

原题

Description:

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target?

Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

原题翻译

描述：

给定一个包含n个实数的数组nums和一个实数target，nums中是否存在元素a，b，c，d，使得a + b + c + d = target？

找到数组中所有唯一的四元组，它们的总和为target。

另外：

结果集中不得包含重复的四元组。

例如：

给定一个数组nums = [1, 0, -1, 0, -2, 2] 和 target = 0.

一个解决方案集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

解法一

主要思想

在3sum的基础上，外层多嵌套一层for循环。

运行速度：超过了89.97%的解答。

内存使用：超过了52.17%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        if (4 * nums[0] > target || 4 * nums[nums.length - 1] < target) {
        return res;
        }
        for (int i = 0; i <= nums.length - 4; i++) {
            if (nums[i] * 4 > target) {
                break;
            }
            if (nums[i] * 4 == target) {
                if (nums[i] == nums[i + 1] && nums[i] == nums[i + 2] && nums[i] == nums[i+3]) {
                    List<Integer> unit = new ArrayList<Integer>();
                    unit.add(nums[i]);
                    unit.add(nums[i]);
                    unit.add(nums[i]);
                    unit.add(nums[i]);
                    res.add(unit);
                }
                break;
            }
            if (i == 0 || nums[i] != nums[i - 1]) { // 避免重复遍历
                int target2 = target - nums[i];
                for (int j = i + 1; j <= nums.length - 3; j++) { // 与3sum相同
                    if (nums[j] * 3 > target2) {
                        break;
                    }
                    if (nums[j] * 3 == target2) {
                        if (nums[j] == nums[j + 1] && nums[j] == nums[j + 2]) {
                            List<Integer> unit = new ArrayList<Integer>();
                            unit.add(nums[i]);
                            unit.add(nums[j]);
                            unit.add(nums[j]);
                            unit.add(nums[j]);
                            res.add(unit);
                        }
                        break;
                    }
                    if (j == i + 1 || nums[j] != nums[j - 1]) {
                        int low = j + 1;
                        int high = nums.length - 1;
                        while (low < high) {
                            int sum = nums[j] + nums[low] + nums[high];
                            if (sum == target2) {
                                List<Integer> unit = new ArrayList<>();
                                unit.add(nums[i]);
                                unit.add(nums[j]);
                                unit.add(nums[low]);
                                unit.add(nums[high]);
                                res.add(unit);
                                low++;
                                high--;
                                while (low < high && nums[low] == nums[low - 1]) { // 避免重复
                                    low++;
                                }
                                while (low < high && nums[high] == nums[high + 1]) { // 避免重复
                                    high--;
                                }
                            } else if (sum > target2){
                                high--;
                            } else {
                                low++;
                            }
                        }
                    }
                }
            } 
        }
        return res;
    }
}